package com.zdb.demo.java.leetcode.q5longestpalindromicsubstring;

public class Solution {

    public static void main(String[] args) {
        String str = "oeabcdedcbaabb";
//        String str = "oabac";
//        String str = "obbc";
        System.out.println(longestPalindrome(str));
    }

    /**
     * 找出字符串中每一个字符对应的回文子串长度[0 ~ 1/2*len]
     * @param s
     * @return
     */
    public static String longestPalindrome(String s) {
        String maxLenStr = "";

        // 最后一个肯定为0
        for(int i=0; i<s.length()-2; i++) {
            int j = i + 1;

            // 判断是否可以回文，j位匹配i,或者i-1位
            int initStep = 0;
            if(s.charAt(i) == s.charAt(j)) {
                initStep = 0;
            } else if(i-1 >=0 && s.charAt(j) == s.charAt(i -1)) {
                initStep = 1;
            } else {
                // 匹配不到回文
                continue;
            }

            int step = expandAroundCenter(s, i-initStep, j);
            int len = 2 * step + 2 + initStep;
            if(maxLenStr.length() < len) {
                maxLenStr = s.substring(i-initStep-step + 1, j+step);
            }


            /**
            int step = 1;
            String ls = "";
            // 查找最大的回文长度
            while(j + step < s.length() && i-initStep-step >= 0) {
                if(s.charAt(i -initStep-step) != s.charAt(j+step)) {
                    break;
                } else {
                    step++;
                }
            }
            // step多了一个1
            ls = s.substring(i-initStep - step + 1, j+step);
            maxLenStr = maxLenStr.length() > ls.length() ? maxLenStr : ls;
             */
        }
        return maxLenStr;
    }

    private static int expandAroundCenter(String s, int left, int right) {
        int L = left, R = right;
        int step = 0;
        while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
            L--;
            R++;
            step ++;
        }
        return step;
    }
    
}